package cn.harperDog.algrithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author hua
 * @description
 * @date 2022/3/3
 *
 * 河面上有N块石头，每块石头的毒性不一，现有一人霸哥要过河，由于河面太宽，霸哥必须踩着石头过河，
 * 霸哥一次最多能跳过两块石头，每踩一块石头霸哥回沾上石头上的全部毒性。
 * 现需要给出霸哥沾上总毒性最少的过河的方式。
 *
 * 举例：河面上的石头和石头的毒性为 [3,1,1,6,4,7,2]，霸哥过河的方式为：跳3块石头远(毒性1)，
 *      再跳2块石头远(毒性4)，再跳3块石头远(毒性0)，霸哥过河后身上的总毒性为1+4=5
 *
 *思路如下：
 *  * 每一次跳跃都有3种情况：分别为 1 2 3
 *  * 即 n 个格子，每个格子可以放 1 2 3中的一个。列出组合的种类
 *  * 在列出的过程中若发现 跳跃的总长度大于等于河中的石头的个数则停止跳跃
 *  * 保存该次过河的跳跃轨迹和总的中毒量
 *  * <p>
 *  * 从每次过河中找出中度量最小的一次过河，输出跳跃轨迹和中毒量
 *
 *  算法：递归
 *
 */
public class JumpStone {
    private static List<Condition> list = new ArrayList<>();


    public static void main(String[] args) {
        int[] stones = new int[]{3, 1, 1, 6, 4, 3, 8, 2, 1, 4, 7, 9, 4, 3, 7, 2};
        int[][] matrix = new int[stones.length][3];
        for (int i = 0; i < matrix.length; i++) {
            matrix[i] = new int[]{1, 2, 3};
        }

        recursion(0, matrix, "", 0, 0, stones);

        //这里可以不用sort。自己写找出最小的即可
        Collections.sort(list, new Comparator<Condition>() {
            @Override
            public int compare(Condition o1, Condition o2) {
                return o1.totalPoison - o2.totalPoison;
            }
        });

        System.out.println("中毒最小的跳跃轨迹" + list.get(0).jumpStack);
        System.out.println("最小的毒量" + list.get(0).totalPoison);
    }

    /**
     * @param index       第几次跳跃
     * @param matrix      二维数组，最外层
     * @param stack       跳跃轨迹，第一次跳几步，第二次跳几步
     * @param jumpTotal   总跳跃部署
     * @param totalPoison 总毒性
     * @param stones      石头及毒性的数组
     */
    public static void recursion(int index, int[][] matrix, String stack, int jumpTotal, int totalPoison, int[] stones) {
        for (int k = 0; k < matrix[index].length; k++) {
            String tmpStack = stack + " " + matrix[index][k];

            int tempJumpTotal = jumpTotal + matrix[index][k];

            int curPoison = 0;

            if (tempJumpTotal > matrix.length) {
                curPoison = 0;
            } else {
                curPoison = stones[tempJumpTotal - 1];
            }

            int tmpTotalPoison = totalPoison + curPoison;

            if ((index == matrix.length - 1)
                    || (tempJumpTotal >= matrix.length)) {
                list.add(new Condition(tmpStack.trim(), tempJumpTotal, tmpTotalPoison));
                //输出跳跃轨迹
                System.out.println("跳跃轨迹" + tmpStack.trim());
                //输出总跳跃次数
                System.out.println("总跳跃次数" + tempJumpTotal);
                //输出总毒性
                System.out.println("总中毒量" + tmpTotalPoison);
            } else {
                recursion(index + 1, matrix, tmpStack, tempJumpTotal, tmpTotalPoison, stones);
            }
        }
    }

    static class Condition {
        private String jumpStack;
        private int totalJump;
        private int totalPoison;

        public Condition() {
        }

        public Condition(String jumpStack, int totalJump, int totalPoison) {
            this.jumpStack = jumpStack;
            this.totalJump = totalJump;
            this.totalPoison = totalPoison;
        }
    }
}
